/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int MaxDepthTree(struct TreeNode* root)//求高度
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		int Ldep = MaxDepthTree(root->left);
		int Rdep = MaxDepthTree(root->right);
		return 1 + ((Ldep >= Rdep) ? Ldep : Rdep);
	}
}
bool isBalanced(struct TreeNode* root) {
	if (root == NULL)
		return true;
	//判断左右子树的深度差
	if (abs(MaxDepthTree(root->left) - MaxDepthTree(root->right)) > 1)
		return false;
	return isBalanced(root->left) && isBalanced(root->right);
}

//上述方法复杂度为O（N*N）,有很多重复的操作，以下为优化后代码
//可以考虑用后序遍历算法
bool _isBalanced(struct TreeNode* root, int* pDepth) {
    if (root == NULL)
    {
        *pDepth = 0;
        return true;
    }
    else
    {
        int leftDepth = 0;
        if (_isBalanced(root->left, &leftDepth) == false)
            return false;

        int rightDepth = 0;
        if (_isBalanced(root->right, &rightDepth) == false)
            return false;

        if (abs(leftDepth - rightDepth) > 1)
            return false;

        *pDepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
        return true;

    }
}
bool isBalanced(struct TreeNode* root) {
    int depth = 0;
    return _isBalanced(root, &depth);
}